12 point(int X
, int Y
) : x(X
), y(Y
) {}
17 ostream
& operator<< (ostream
& out
, const point
& c
)
19 out
<< "(" << c
.x
<< "," << c
.y
<< ")";
23 //P es un polígono ordenado anticlockwise.
24 //Si es clockwise, retorna el area negativa.
25 //Si no esta ordenado retorna pura mierda.
27 double area(const vector
<point
> &p
){
29 for (int i
=0; i
<p
.size(); ++i
){
30 int j
= (i
+1) % p
.size();
31 r
+= p
[i
].x
*p
[j
].y
- p
[j
].x
*p
[i
].y
;
36 //retorna si c esta a la izquierda de el segmento AB
37 inline int cross(const point
&a
, const point
&b
, const point
&c
){
38 return (b
.x
-a
.x
)*(c
.y
-a
.y
) - (c
.x
-a
.x
)*(b
.y
-a
.y
);
41 //Self < that si esta a la derecha del segmento Pivot-That
42 bool angleCmp(const point
&self
, const point
&that
){
43 return( cross(pivot
, that
, self
) < 0 );
46 inline int distsqr(const point
&a
, const point
&b
){
47 return (a
.x
- b
.x
)*(a
.x
- b
.x
) + (a
.y
- b
.y
)*(a
.y
- b
.y
);
50 //vector p tiene los puntos ordenados anticlockwise
51 vector
<point
> graham(vector
<point
> p
){
53 sort(p
.begin(), p
.end(), angleCmp
);
54 //Ordenar por ángulo y eliminar repetidos.
55 //Si varios puntos tienen el mismo angulo se borran todos excepto el que esté más lejos
56 for (int i
=1; i
<p
.size()-1; ++i
){
57 if (cross(p
[0], p
[i
], p
[i
+1]) == 0){ //Si son colineales...
58 if (distsqr(p
[0], p
[i
]) < distsqr(p
[0], p
[i
+1])){ //Borrar el mas cercano
59 p
.erase(p
.begin() + i
);
61 p
.erase(p
.begin() + i
+ 1);
67 vector
<point
> chull(p
.begin(), p
.begin()+3);
70 for (int i
=3; i
<p
.size(); ++i
){
71 while ( chull
.size() >= 2 && cross(chull
[chull
.size()-2], chull
[chull
.size()-1], p
[i
]) < 0){
72 chull
.erase(chull
.end() - 1);
74 chull
.push_back(p
[i
]);
83 while (cin
>> n
&& n
){
85 point
min(10000, 10000);
87 for (int i
=0; i
<n
; ++i
){
90 p
.push_back(point(x
,y
));
91 if (y
< min
.y
|| (y
== min
.y
&& x
< min
.x
)){
96 double tileArea
= fabs(area(p
));
98 //Destruye el orden cw|ccw poligono, pero hay que hacerlo por que Graham necesita el pivote en p[0]
99 swap(p
[0], p
[minPos
]);
101 double chullArea
= fabs(area(graham(p
)));
103 printf("Tile #%d\n", tileNo
++);
104 printf("Wasted Space = %.2f \%\n\n", (chullArea
- tileArea
) * 100.0 / chullArea
);